package LeetCode;


import java.util.HashMap;
import java.util.Map;

public class No105 {
    private Map<Integer, Integer> indexMap;

    public static void main(String[] args) {
        int[] preorder = {3,9,20,15,7};
        int[] inorder = {9,3,15,20,7};
        System.out.println();
    }
    public TreeNode mybuildTree(int[] preorder, int[] inorder, int preleft, int preright, int inleft, int inright){
        if(preleft>preright) return null;
        int mid = indexMap.get(preorder[preleft]);
        TreeNode root = new TreeNode(preorder[preleft]);
        int len = mid-inleft;
        root.left = mybuildTree(preorder,inorder,preleft+1,preleft+len,inleft,mid-1);
        root.right = mybuildTree(preorder,inorder,preleft+len+1,preright,mid+1,inright);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        indexMap = new HashMap<Integer,Integer>();
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i],i);
        }
        return mybuildTree(preorder,inorder,0,preorder.length-1,0,inorder.length);
    }
}
